package random;

import java.util.ArrayList;

/**
 * 区域和检索-数组不可变
 *
 * 给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
 * 实现 NumArray 类：
 * NumArray(int[] nums) 使用数组 nums 初始化对象
 * int sumRange(int i, int j) 返回数组 nums 从索引i到j（i≤j）范围内元素的总和，
 * 包含i、j两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/range-sum-query-immutable
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class L303 {


    /*
    前缀和方法，防止频繁调用sumRange方法导致时间复杂度过大
     */
    static class numArray {
        int[] sums;

        public numArray(int[] nums) {
            int n = nums.length;
            sums = new int[n + 1];
            for (int i = 0; i < n; i++) {
                sums[i + 1] = sums[i] + nums[i];
            }
        }

        public int sumRange(int i, int j) {
            return sums[j + 1] - sums[i];
        }
    }

    public static void main(String[] args) {

        numArray numArray = new numArray(new int[]{-2, 0, 3, -5, 2, -1});
        int i = numArray.sumRange(0, 5);
        System.out.println(i);
    }
}
